package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         51,
		Discription: "N皇后",
		Level:       3,
		Labels: map[string]int{
			"哈希表": 1,
			"回溯":  1,
			"递归":  1,
			"类数独": 1,
		},
	})
}

//逐行递归确定答案
func SolveNQueens(n int) [][]string {
	rows := make([]bool, n)
	//i-j+n-1
	slash1 := make([]bool, 2*n-1)
	//i+j
	slash2 := make([]bool, 2*n-1)

	strs := make([]string, n)
	res := make([][]string, 0)

	var dfs func(int)
	dfs = func(i int) {
		if i == n {
			res = append(res, append([]string(nil), strs...))
			return
		}

		//每一行的字符串用[]byte表示，方便回溯后复原
		colBytes := make([]byte, n)
		for k := range colBytes {
			colBytes[k] = '.'
		}

		for j := 0; j < n; j++ {
			if rows[j] || slash1[i-j+n-1] || slash2[i+j] {
				continue
			}

			rows[j] = true
			slash1[i-j+n-1] = true
			slash2[i+j] = true
			colBytes[j] = 'Q'
			strs[i] = string(colBytes)
			dfs(i + 1)
			rows[j] = false
			slash1[i-j+n-1] = false
			slash2[i+j] = false
			colBytes[j] = '.'
		}
	}

	dfs(0)
	return res
}
